package com.ztom.hard;

/**
 * 1 ~ n 整数中 1 出现的次数
 * <p>
 * https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/
 *
 * @author ZhangTao
 */
public class Code04CountDigitOne {

    public int countDigitOne1(int n) {
        if (n == 0) {
            return 0;
        }
        int count = 0;
        for (int i = 1; i <= n; i++) {
            count += count(i);
        }
        return count;
    }

    private int count(int x) {
        int count = 0;
        while (x > 0) {
            if (x % 10 == 1) {
                count++;
            }
            x /= 10;
        }
        return count;
    }

    public int countDigitOne(int n) {
        // mulk 表示 10^k
        // 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）
        // 但为了让代码看起来更加直观，这里保留了 k
        long mulk = 1;
        int ans = 0;
        for (int k = 0; n >= mulk; ++k) {
            ans += (n / (mulk * 10)) * mulk + Math.min(Math.max(n % (mulk * 10) - mulk + 1, 0), mulk);
            mulk *= 10;
        }
        return ans;
    }
}
